package algorithm.leetcode.I1to100;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 一个经典的例子,如何在全排列中控制重复
 */

public class Q47 {

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> global = new LinkedList<>();
        // 控制重复语法糖1/3
        Arrays.sort(nums);
        boolean[] isUsed = new boolean[nums.length];
        dfs(global, new LinkedList<>(), nums, isUsed);
        return global;
    }

    private void dfs(List<List<Integer>> global,
                     LinkedList<Integer> curr,
                     int[] nums,
                     boolean[] isUsed) {
        if (curr.size() == nums.length) {
            global.add(new LinkedList<>(curr));
        }

        // 控制重复语法糖2/3
        int lastUsed = -1;
        for (int i = 0; i < nums.length; i++) {
            // 下面两行,控制重复语法糖3/3
            if (isUsed[i]) lastUsed = i;
            else if (!isUsed[i] && (lastUsed == -1 || nums[lastUsed] < nums[i])) {
                curr.addLast(nums[i]);
                isUsed[i] = true;
                dfs(global, curr, nums, isUsed);
                isUsed[i] = false;
                curr.removeLast();
            }
        }

    }

}
